/*
 * 
 * Prefix tree funtions for learning a GSMP
 *
 */
/* FILE: $Id: prefix_tree.c 20 2011-09-30 20:05:09Z apedro $ */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#ifdef MATLAB_MEX_FILE   
#include "mex.h"
#define debug_error(s) \
mexErrMsgTxt(s)
#else
#define debug_error(s) \
        printf(s); \
        exit(EXIT_FAILURE);
#endif

#include "itf_debug.h"

#include "prefix_tree.h"
#include "path.h"

/* This block defines the dobule linked list funtions to the clock samples */
GEN_DLINKEDLIST_FUNCTIONS(dll_clock, clock_l, clock_n, double *);

void clock_debug(clock_l *pl, clock_n *node) {
    
    DEBUG_PRINT((FDEBUG, "%f", node->data));
    node = node->next;
    
    for(;node != NULL;) {
        DEBUG_PRINT((FDEBUG, "-> %f ", *(node->data)));
        
        node = node->next;
    }
    
    DEBUG_PRINT((FDEBUG, "| %d\n",pl->n));
}
/* --------------------------------------------------------------------- */

/* This block instanciates the NTRIE funtions                            */
/* --------------------------------------------------------------------- */
ntrieNode *pt_create_ntrienode(evnode *node, unsigned int event) {
    ntrieNode *ntode;
    
    ntode = malloc(sizeof(ntrieNode));
    
    ntode->key = (size_t) event;
    ntode->node = node;
    ntode->removed = 0;
    ntode->clks = NULL;
    
    return(ntode);
}

void pt_destroy_ntrienode(ntrieNode *ntode) {
    free(ntode);
}

// -------

ntrieNode *pt_create_node_nt2(unsigned int key) {
    ntrieNode *node_nt;
    
    node_nt = malloc(sizeof(ntrieNode));
    node_nt->key = (size_t) key;
    node_nt->node = NULL;
    return(node_nt);
}

ntrieNode *pt_change_node_nt(ntrieNode *node_nt, evnode *node) {
    node_nt->node = node;
    return(node_nt);
}

// -------

ntrie *pt_create_nt() {
    ntrie *nt;
    nt = malloc(sizeof(ntrie));
    NEDTRIE_INIT(nt);
    
    return nt;
}

void pt_destroy_nt(ntrie *nt) {
    ntrieNode *node_nt;
    
    node_nt = NEDTRIE_MIN(ntrie_s, nt);
    while(node_nt != NULL) {
        NEDTRIE_REMOVE(ntrie_s, nt, node_nt);
        pt_destroy_ntrienode(node_nt);
        
        node_nt = NEDTRIE_MIN(ntrie_s, nt);
    }
    
    free(nt);
}

/* --------------------------------------------------------------------- */

/* This block instanciates the heap 'Merge nodes' functions               */
/* --------------------------------------------------------------------- */
heap_mg_el *create_heap_mg_el(heap_mg *heap, evnode *x1, evnode *x2) {
    heap_mg_el *h_el;
    
    h_el = (heap_mg_el *) malloc(sizeof(heap_mg_el));
    h_el->key = (size_t) heap->id_heap;
    heap->id_heap = heap->id_heap + 1;
    DEBUG_PRINT((FDEBUG, "==== ++++ %d\n", heap->id_heap));
    h_el->x1 = x1;
    h_el->x2 = x2;
    
    return(h_el);
}

void destroy_heap_mg_el(heap_mg_el *h_el) {
    free(h_el);
}
/* --------------------------------------------------------------------- */

/**/
GEN_DLINKEDLIST_FUNCTIONS(dll_inward, inward_l, inward_n, ntrieNode *);
/**/


/* Create a trie of new evnodes with enought in (E,T)n tuple vector. 'n' is the size of vector. */
static evnode *pt_evnode(psa *trie, path_l *path, evnode *parent) {
    int i, flag = 0;
    path_n *act_node;
    evnode *node, *nodeback, *firstnode;
    ntrieNode *node_nt;
    clock_n *clk_node;
    
    assert(path != NULL && trie != NULL);
    
    DEBUG_PRINT((FDEBUG, "pt_evnode start {\n"));
    
    act_node = path->firstNode;
    nodeback = parent;
    
    assert(act_node != NULL);
    
    for (i=0; act_node != NULL; i++, nodeback = node, act_node = act_node->next) {
        
        if (i == 0)
            node = firstnode = malloc(sizeof(evnode));
        else
            node = malloc(sizeof(evnode));
        
        
        if (node == NULL)
            debug_error("Malloc: Null allocation 'sizeof(evnode)'.");
        
        
        /* if it is needed realloc the nodes pinter */
        if (trie->n+1 > trie->nodeArraySize-1) {
            trie->nodeArraySize = trie->nodeArraySize + 1000;
            trie->nodeArray = realloc(trie->nodeArray, trie->nodeArraySize * (sizeof(evnode *)));
        }
        
        assert(trie->n < trie->nodeArraySize);
        
        trie->nodeArray[trie->n++] = (evnode *) node;
        
        /* Make mapping to path */
        act_node->data.t_node = node;
        
        node->nid = trie->n;
        node->eid = act_node->data.ev_id;
        node->ntimes = 1;
        node->removed = 0;
        node->remp = NULL;
        
        if (nodeback == NULL)
            node->deg = 1;
        else
            node->deg = nodeback->deg + 1;
        
        node->clk_samples = dll_clock_newlist();
        clk_node = dll_clock_newnode(&(act_node->data.clk));
        if (clk_node == NULL)
            debug_error("Null pointer: 'dll_new_node(void *data)'.");
        
        DEBUG_PRINT((FDEBUG, "**** time: %f %f\n", act_node->data.clk, clk_node->data));
        dll_clock_insertbeginning(node->clk_samples, clk_node);
        
        
        node->child = pt_create_nt();
        node->inward = dll_inward_newlist();
        node->parent = nodeback;
        
        if (nodeback != NULL && i != 0) {
            DEBUG_PRINT((FDEBUG, "ADD child on %d to %d event: %d\n", nodeback->nid, node->nid, node->eid));
            /* Create new trie node */
            node_nt = pt_create_ntrienode(node, node->eid); //pt_create_node_nt(node);
            
            if (node_nt == NULL)
                debug_error("Null pointer: 'pt_create_node_nt(node)'.");
            
            node_nt->node->nt_node = node_nt;
            
            // Add node child
            NEDTRIE_INSERT(ntrie_s, nodeback->child, node_nt);
            
            DEBUG_PRINT((FDEBUG, "ADDED\n"));
        }
        else if (nodeback == NULL && i == 0) {
            node_nt = pt_create_ntrienode(node, node->eid); //pt_create_node_nt(node);
            
            if (node_nt == NULL)
                debug_error("Null pointer: 'pt_create_node_nt(node)'.");
            
            node_nt->node->nt_node = node_nt;
        }
    }
    
    DEBUG_PRINT((FDEBUG, "\n}\n"));
    
    assert(firstnode != NULL);
    
    return firstnode;
}

void pt_insert_word(psa *trie, path_l *path, unsigned int i, path_n *p1, evnode *node)
{
    path_l *x;
    ntrieNode *node_nt;
    evnode *node_tmp;
    
    // Create all path missing
    x = dll_path_newlist();
    x->firstNode = p1;
    x->lastNode = path->lastNode;
    x->n = path->n - (i-1);

    node_tmp = pt_evnode(trie, x, node);
    node_nt = pt_create_ntrienode(node_tmp, node_tmp->eid);//pt_create_node_nt(pt_evnode(trie, x, node));
    node_nt->node->nt_node = node_nt;

    free(x);

    if (node_nt == NULL)
        debug_error("Null pointer: 'pt_create_node_nt(pt_evnode(trie, x, node)))'.");

    // Add node to child ntrie
    NEDTRIE_INSERT(ntrie_s, node->child, node_nt);
}

void pt_insert_clock(evnode *nodechild, path_n *p) 
{
    clock_n *clk_node;
    
    nodechild->ntimes++;
    clk_node = dll_clock_newnode(&(p->data.clk));
    if (clk_node == NULL)
        debug_error("Null pointer: 'dll_new_node(void *data)'.");

    dll_clock_insertbeginning(nodechild->clk_samples, clk_node);
}

/* Search and refresh a trie for one sample (E,T)n */
static void pt_search(psa *trie, path_l *path, unsigned int i, path_n *p, evnode *node, evnode *nodechild) {
    
    ntrieNode tmp_node_nt, *node_nt;
    unsigned int n;
    
    
    DEBUG_PRINT((FDEBUG, "Called pt_search ...\n"));
    
    n = path->n;
    tmp_node_nt.node = NULL;
    
    /* Review this */
    DEBUG_PRINT((FDEBUG, "N: %d, I: %d\n", n, i));
    if (i>n)
        return;
    
    if (p == NULL) {
        path->lastNode->prev->data.t_node = node;
        if(nodechild == NULL) {
            pt_insert_word(trie, path, i, path->lastNode, node);
            DEBUG_PRINT((FDEBUG, "Clock: %f\n", path->lastNode->data.clk));
        }
        else {
            path->lastNode->data.t_node = nodechild;
            pt_insert_clock(nodechild, path->lastNode);
        }
        return;
    }
    /* Review this */
    
    p->prev->prev->data.t_node = node;
    
    if (nodechild == NULL) {
        DEBUG_PRINT((FDEBUG, "NULL Chield i: %d id: %d \n", i, node->eid));
        
        pt_insert_word(trie, path, i, p->prev, node);

        return;
    }
    else {
        pt_insert_clock(nodechild, p->prev);
        
        /* Map node of path with trie node when exists a children */
        //if(p->prev->prev != NULL)
        //    p->prev->prev->data.t_node = node;
        
        DEBUG_PRINT((FDEBUG, "Node refresh!\n"));
        
        DEBUG_PRINT((FDEBUG, "Pointers: %p\n", nodechild->child));
        
        tmp_node_nt.key = p->data.ev_id;
        tmp_node_nt.node = NULL;
        node_nt = NEDTRIE_FIND(ntrie_s, nodechild->child, &tmp_node_nt);
        
        DEBUG_PRINT((FDEBUG, "Find pointer: %p\n", node_nt));
        
        if (node_nt != NULL) {
            //mexPrintf("Node NOT NULL\n");
            pt_search(trie, path, i+1, p->next, nodechild, node_nt->node);
        }
        else {
            //mexPrintf("Node NULL\n");
            pt_search(trie, path, i+1, p->next, nodechild, NULL);
        }
        
        return;
    }
}

/* This funtion inserts one sample path to the prefix tree */
void pt_insert(psa *trie, path_l *path) {
    ntrieNode tmp_node_nt, *node_nt;
    path_n *p;
    
    DEBUG_PRINT((FDEBUG, "Trie size: %d\nCALL pt_insert...\n", trie->n));
    assert(trie != NULL && path != NULL);
    
    p = path->firstNode;
    assert(p != NULL);
    
    if (trie->n == 0 && trie->root == NULL) {
        DEBUG_PRINT((FDEBUG, "Init trie ...\n"));
        trie->root = pt_evnode(trie, path, NULL);
        assert(trie->root != NULL);
    }
    else {
        DEBUG_PRINT((FDEBUG, "Continue filling the trie ...\n"));
        tmp_node_nt.node = NULL;
        tmp_node_nt.key = (size_t) p->next->data.ev_id;
        node_nt = NEDTRIE_FIND(ntrie_s, trie->root->child, &tmp_node_nt);
        
        DEBUG_PRINT((FDEBUG, "Pointers: %p\n", node_nt));
        
        if (node_nt != NULL) {
            DEBUG_PRINT((FDEBUG, "Find: %d, encountered: %d\n", tmp_node_nt.key, node_nt->key));
            pt_search(trie, path, 2, p->next->next, trie->root, node_nt->node);
        }
        else {
            DEBUG_PRINT((FDEBUG, "Find: %d, encountered: NULL\n", tmp_node_nt.key));
            pt_search(trie, path, 2, p->next->next, trie->root, NULL);
        }
        
        
        //path->firstNode->next->data.t_node = trie->root;
        trie->root->ntimes++;
    }
}

int evnodecmp_c(evnode *n1, evnode *n2) {
    ntrieNode *e1_nt, *e2_nt;
    
    if (n1->child->count == n2->child->count) {
        /* Use the defined order to the children field */
        
        e1_nt = NEDTRIE_MIN(ntrie_s, n1->child);
        e2_nt = NEDTRIE_MIN(ntrie_s, n2->child);
        
        for (;e1_nt != NULL && e2_nt != NULL;
            e1_nt = NEDTRIE_NEXT(ntrie_s, n1->child, e1_nt),
            e2_nt = NEDTRIE_NEXT(ntrie_s, n2->child, e2_nt)) {
            
            //printf("evnodecmp_c: E1: %p, %u\n", e1_nt, e1_nt->key);
            //printf("evnodecmp_c: E2: %p, %u\n", e2_nt, e2_nt->key);
            
            if(e1_nt->node->eid == e2_nt->node->eid)
                continue;
            else if (e1_nt->node->eid > e2_nt->node->eid)
                return -1;
            else
                return 1;
        }
        
        return 0;
    }
    else if (n1->child->count > n2->child->count)
            return -1;
        else
            return 1;
}

/* Create the trie */
psa *pt_create() {
    psa *trie;
    trie = malloc(sizeof(psa));
    if (trie == NULL)
        debug_error("Malloc: Null allocation 'sizeof(psa)'.");
    trie->n = 0;
    trie->root = NULL;
    trie->nodeArraySize = 1000;
    trie->nodeArray = malloc(sizeof(evnode *) * trie->nodeArraySize); /* Store the pointer array of 1000 elements */
    
    // Initialize h_mg
    trie->h_mg = (heap_mg *) malloc(sizeof(heap_mg));
    NEDTRIE_INIT(trie->h_mg);
    trie->h_mg->id_heap = 1;
    
    trie->parameters = NULL;
    
    return trie;
}

/* Free the node from the trie */
void pt_free_node(evnode *node) {
    
    dll_clock_freelist(node->clk_samples);
    
    pt_destroy_nt(node->child);
    
    free(node);
}

/* function to destroy the prefix tree*/
void pt_free_prefix_tree(psa *trie) {
    unsigned int i;
    
    // Free all nodes
    for(i=0; i<trie->n; i++) {
        pt_free_node(trie->nodeArray[i]);
    }
    
    // remove node array
    free(trie->nodeArray);
    
    if(trie->h_mg->count == 0)
        free(trie->h_mg);
    else {
        // remove each element
        
    }
    
    free(trie);
}

double *pt_create_clock_array(clock_l *clk_list, unsigned int size) {
    unsigned int i;
    double *clarray;
    clock_n *clnode;
    
    // For all elements of the clock list
    clarray = (double *) malloc(sizeof(double)*size);
    
    for(i=0, clnode = clk_list->firstNode; clnode != NULL && i<size; i++, clnode = clnode->next) {
        clarray[i] = *(clnode->data);
    }
    
    return clarray;
}

/*  */
void normalize_inward(psa *trie) {
    unsigned int i;
    ntrieNode node_nt, *tmp_n;
    // for all nodes
    for(i=0; i<trie->n; i++) {
        if (trie->nodeArray[i]->parent != NULL) {
            node_nt.key = trie->nodeArray[i]->eid;
            node_nt.node = NULL;
            tmp_n = NEDTRIE_FIND(ntrie_s, trie->nodeArray[i]->parent->child, &node_nt);
            
            // Copy clock values to an array
            tmp_n->clks_size = trie->nodeArray[i]->clk_samples->n;
            tmp_n->clks = pt_create_clock_array(trie->nodeArray[i]->clk_samples, trie->nodeArray[i]->clk_samples->n);        
            
            dll_inward_insertend(trie->nodeArray[i]->inward, dll_inward_newnode(tmp_n));
            trie->nodeArray[i]->parent = NULL;
            trie->nodeArray[i]->eid = 0;
            // Free clock list
            dll_clock_freelist(trie->nodeArray[i]->clk_samples);
            trie->nodeArray[i]->clk_samples = NULL;
        }
    }
}

/*static int cmp_dln(const void *p1, const void *p2) {
    DoublyLinkedNode *n1 = * (DoublyLinkedNode * const *) p1;
    DoublyLinkedNode *n2 = * (DoublyLinkedNode * const *) p2;
    
    return ((evnode *)n1->data)->eid - ((evnode *)n2->data)->eid;
}

void pt_sort(psa *trie) {
    unsigned int i, j, size;
    DoublyLinkedNode *node;
    DoublyLinkedNode **rl;
    
    mexPrintf("Size trie: %d\n", trie->n);
    for(i=0; i < trie->n; i++) {
        node = trie->nodeArray[i]->child->firstNode;
        size = trie->nodeArray[i]->child->n;
        
        mexPrintf("Size: %d\n", size);
        
        if(size > 1) {
            
            // Convert list to array
            rl = (DoublyLinkedNode **) malloc(sizeof(DoublyLinkedNode *) * size);

            for(j=0; node != NULL; j++) {
                rl[j] = node;
                node = node->next;
            }

            // Order array
            qsort(rl, size, sizeof(DoublyLinkedNode *), cmp_dln);
            
            //for(j=0; j<size; j++)
            //    mexPrintf("%d ", ((evnode *)rl[j]->data)->eid);
            //mexPrintf("\n");

            trie->nodeArray[i]->child->firstNode=NULL;
            trie->nodeArray[i]->child->lastNode=NULL;
            trie->nodeArray[i]->child->n=0;

            // Convert list to array
            for(j=0; j<size; j++)
                dll_insertEnd(trie->nodeArray[i]->child, rl[j]);

            free(rl);
        }
    }
}*/

/*void tr_tofile(psa *trie, char *filename) {
    FILE *dot;
    char *path;
    
    dot = fopen(filename, "w");
    if (dot != NULL) {
        fprintf(dot, "digraph graphname { \nsize=\"200\";\nnode [color=lightblue, style=filled];\n");
        path = malloc(sizeof(char)*100);
        sprintf(path,"");
        tr_tofile2(dot, trie->root, path);
        fprintf(dot, "}\n");
    
        fclose(dot);
    }
}

void tr_tofile2(FILE *dot, evnode *node, char *path) {
    DoublyLinkedList *nodelist;
    DoublyLinkedNode *x, *y;
    
    clock_n *clx, *cly;
    
    evnode *childnode;
    char *sampleclock;
    int size, size_init, size_end;
    double clx_value;
    
    sampleclock = malloc(sizeof(char)*100);
    
    nodelist = node->child;
    
    if (nodelist == NULL)
        return;
    
    // for each node child
    for (x=nodelist->firstNode; x!=NULL;) {
        y = x->next;
        
        childnode = x->data;
        
        
        assert(strlen(path)+1 < 100);
        
        sprintf(sampleclock,"");
        // For each clock in childnode
        for (clx=childnode->clk_samples->firstNode; clx != NULL;) {
            cly = clx->next;
            
            clx_value = clx->data;
            
            sprintf(sampleclock,"%s%.2f ",sampleclock, clx_value);
            
            clx=cly;
        }
        mexPrintf("S: %s\n", sampleclock);
        
        size_init = (unsigned int) strlen(path);
        if (strlen(path) > 0) {
            fprintf(dot, "\"%s.%d\" -> \"%s.%d.%d\" [label=\"%d P:%d/%d SC:|%s|\"];\n", path, node->eid, path, node->eid, childnode->eid, childnode->eid, childnode->ntimes, node->ntimes, sampleclock);
            sprintf(path, "%s.%d", path, node->eid);
        }
        else {
            fprintf(dot, "\"%d\" -> \"%d.%d\" [label=\"%d P:%d/%d SC:|%s|\"];\n", node->eid, node->eid, childnode->eid, childnode->eid, childnode->ntimes, node->ntimes, sampleclock);
            sprintf(path, "%d", node->eid);
        }
        size_end = (unsigned int) strlen(path);
        
        size = size_end-size_init;
        
        //mexPrintf("%s\n", path);
        
        tr_tofile2(dot, childnode, path);
        
        path[(strlen(path))-size] = '\0';
        
        x=y;
    }
    
    free(sampleclock);
    
}*/

/*static void pt_debug_path(evnode *node) {
    
    ntrieNode *x;
    
    mexPrintf("Node: %p, %d, (%d,%d) -> [", node, node->deg, node->nid, node->eid);
    
    if (node->child->count > 0) {
        NEDTRIE_FOREACH(x, ntrie_s, node->child) {
            mexPrintf("(%d, %d), ", x->node->nid, x->node->eid);
        }
    }
    else {
        mexPrintf("]\n");
        return;
    }
    
    mexPrintf("]\n");
    
    NEDTRIE_FOREACH(x, ntrie_s, node->child) {
        if (x->node->deg > node->deg)
            pt_debug_path(x->node);
    }
}*/

/*void pt_debug(psa *trie) {
    
    ntrieNode *x;
    
    mexPrintf("Root: %p, %d, (%d,%d) -> [",trie->root, trie->root->deg, trie->root->nid, trie->root->eid);
    // print node childs
    NEDTRIE_FOREACH(x, ntrie_s, trie->root->child) {
        mexPrintf("(%d, %d), ", x->node->nid, x->node->eid);
    }
    mexPrintf("]\n");
    
    NEDTRIE_FOREACH(x, ntrie_s, trie->root->child) {
        pt_debug_path(x->node);
    }
}*/

void pt_debug(psa *trie) {
    unsigned int i;
    ntrieNode *x;
    evnode *node;
    
    for(i=0; i < trie->n; i++) {
        node = trie->nodeArray[i];
        
        mexPrintf("Node: %p, |C|: %d, %d, (%d,%d) -> [", node, node->child->count, node->deg, node->nid, node->eid);
        NEDTRIE_FOREACH(x, ntrie_s, node->child) {
            mexPrintf("(%d, %d), ", x->node->nid, x->node->eid);
        }
        mexPrintf("]\n");
    }
}

/*void pt_debug_trieNodes(psa *trie) {
    unsigned int i;
    DoublyLinkedNode *node;
    
    for(i=0; i<trie->n; i++) {
        mexPrintf("|");
        node = trie->nodeArray[i]->child->firstNode;
        while(node != NULL) {
            mexPrintf("%d ", ((evnode *)node->data)->eid);
            node = node->next;
        }
        mexPrintf("| ");
    }
    mexPrintf("\n");
}

void tr_debug(psa *trie) {
    mexPrintf("DEBUG...\n");
    if (trie == NULL)
        debug_error("Null pointer: 'trie'.");
    else {
        if (trie->root != NULL) {
            mexPrintf("Data Init: %d %d\n", trie->root->eid, trie->root->ntimes);
            tr_debug2(trie->root->child,2);
        }
        else
            debug_error("Null pointer: 'trie->root'.\n");
    }
}

void tr_debug2(DoublyLinkedList *nodelist, int i) {
    DoublyLinkedNode *x, *y;
    evnode *node;
    int j = 0;
    
    if (nodelist == NULL)
        return;
    
    // for each root child
    //mexPrintf("List Size: %d\n", nodelist->n);
    for (x=nodelist->firstNode; x!=NULL; j++) {
        y = x->next;
        
        node = x->data;
        mexPrintf("Data %d: %d %d\n", i, node->eid, node->ntimes);
        tr_debug2(node->child,i+1);
        //mexPrintf("STEP %d %d\n", i, j);
        
        x=y;
    }
    
}*/
